This invention relates to an automatic wiring method. More particularly, the invention relates to an automatic wiring method for performing wiring which turns at angles in units of 90.degree. between predetermined pins based upon part placement data, such as part pin position or part pin shape, and wiring data which specifies the positions of pins that will be at identical potential, and performing automatic wiring processing in which diagonal wiring is added at appropriate locations.
The demand for high-density mounting of parts in recent years has led to parts with greater numbers of pins and to reduced spacing between pins, as a result of which the automatic wiring of printed circuit boards has become more difficult. Consequently, there is demand for an automatic wiring method that is capable of dealing with high-density mounting.
Known methods of finding wiring routes in automatic wiring processing include the maze method, also referred to as Lee's algorithm, the line search method and the area search method. However, in order to execute automatic wiring processing efficiently, all of these methods entail the performance of simple modeling, in which obstacles (part pins, circuit board lands and the like) are put into the form of rectangular models, by way of example. In order to avoid these obstacles, mainly curved wiring processing is performed in which turns are made in 90.degree. units.
FIGS. 14(a) and (b) are diagrams for describing the line search method. Numeral 1 denotes a printed circuit board, 2a-2d represent obstacles, and A, B represent the position of pins that are desired to be wired together. According to the line search method, horizontal and vertical lines (wiring lines) that are capable of being are generated successively from the two pin positions A, B that are to be wired, and a printed wiring route is found by determining whether a route is completed by these line segments. More specifically, horizontal line segments are drawn from each of the two points A and B until these line segments strike an obstacle. These line segments are designated provisional line segments L.sub.01, L.sub.01 ' of level 0. If the provisional line segments of level 0 overlap, then this means that a route connecting A and B has been found. A printed wiring route can be discovered by retracing the line segments in the opposite direction.
If these provisional line segments do not overlap, then vertical line segments are generated as provisional line segments L.sub.11, L.sub.12, L.sub.13, . . . ; L.sub.11 ', L.sub.12 ', L.sub.13 ' . . . of level 1 from all points (points having a spacing of one pitch on the wiring line) on the provisional line segment of level 0. If provisional line segments generated from each of the points A, B intersect, a printed wiring route is constructed by retracing these line segments in the opposite direction. If a route still cannot be found, provisional line segments of level 2, level 3 and so on are generated.
In the example of FIGS. 14(a) and (b) a printed wiring route PPT [FIG. 14(b)] is discovered by the intersection between a line segment L.sub.21 of level 2 generated from the A side and the line segment L.sub.11 ' of level 1 generated from the B side.
FIGS. 15(a)-(c) are views for describing the area search method. Numeral 5 denotes a printed circuit board, 6a-6f designate pads, and 7a-7d represent patterns that have already been wired. When a search is made for a printed wiring route from a source pad 6a to a target pad (not shown), a rectangular expansion area 7a, which is the result of expanding the area of the source pad 6a in all directions until it strikes an obstacle, is obtained [see FIG. 15(b)]. Here the edge (indicated by the dashed line) contacting the obstacle is referred to as a "blocked edge" and is excluded from the area which is the object of the search. Edges not contacting the obstacle are referred to as "free edges". These portions are expanded until they similarly strike obstacles, whereby rectangular expansion areas 8a-8d are found [see FIG. 15(c)]. Thereafter, the free edges of these expansion areas are expanded in similar fashion, thereby successively obtaining expansion areas 9a, 9a' . . . and so on. Eventually, the target pad or an expansion area from the target pad is reached to find the printed wiring route. For the details of the area search method, refer to A. C. Finch et. al. "A Method of Gridless Routing of Printed Circuit Boards", Proceedings of the 22nd Design Automation Conference, 1985, pp. 509-515.
In a case where diagonal wiring (45.degree. printed wiring) is necessary after a route is obtained by wiring processing at turns in 90.degree. units, e.g., in a case where a 45.degree. turn results in a shorter wiring distance and therefore is advantageous in terms of electrical characteristics, a 90.degree. turn is shaped into a 45.degree. turn, as illustrated in FIG. 16. However, since diagonal wiring processing can not be performed automatically, the operation to obtain such diagonal wiring is troublesome.
With wiring at 90.degree. turns, the number of wiring lines capable of being wired between part pins is limited and therefore a problem which arises is that the method cannot cope with high-density mounting.
Furthermore, with increasingly higher density mounting, parts have recently appeared having pin arrays that cannot be wired without using diagonal (45.degree.) printed wires at the time of wiring processing. With the conventional automatic wiring method using 90.degree. turns, these parts cannot be wired, and such a method cannot cope with the mounting of parts in higher densities. FIGS. 17(a) and (b) are diagrams for describing this problem. This represents a case in which ten wiring lines (tracks) are capable of being arranged in one grid (2.54 mm). With conventional automatic wiring processing using 90.degree. turns, this processing is carried out by making the shapes of obstacles (part pins) 5a-5e all approximate minimum rectangular shapes 5a'-5e', which include these shapes, in order to raise the speed of processing. Consequently, whereas two wiring lines L.sub.11, L.sub.12 ; L.sub.21, L.sub.22 ; L.sub.31, L.sub.32 ; L.sub.41, L.sub.42 can be arranged between mutually adjacent part pins with diagonal wiring, as depicted in FIG. 17(b), not even a single wiring line can be provided with wiring that relies upon 90.degree. turns, as illustrated in FIG. 17(a).
Accordingly, though it has been considered to perform diagonal wiring automatically by a diagonal wiring algorithm instead of using the 90.degree.-turn wiring processing, this is difficult to realize because the processing is too complicated.